package br.ufc.great;

import java.io.Serializable;
import java.util.Enumeration;
import java.util.Hashtable;
import java.util.Vector;

/**
 * 
 * @author Leonardo Oliveira Moreira
 *
 * Classe utilizado para representar um grafo
 */
public class Graph implements Serializable {

	private Hashtable<Vertex, Vector<Vertex>> graph;
	
	private boolean circle;
	
	public Graph() {
		graph = new Hashtable<Vertex, Vector<Vertex>>();
		circle = false;
	}
	
	public synchronized Graph getGraph() {
		return this;
	}
	
	public synchronized Hashtable<Vertex, Vector<Vertex>> getData(){
		return graph;
	}
	
	public synchronized void unionGraph(Hashtable<Vertex, Vector<Vertex>> newGraph) {
		Enumeration<Vertex> newKeys = newGraph.keys();
		// percorre todos os vertices do novo grafo
		while (newKeys.hasMoreElements()) {
			// pega um vertice do novo grafo
			Vertex newVertex = newKeys.nextElement();
			boolean foundVertex = false;
			Enumeration<Vertex> keys = graph.keys();
			// percorre todos vertices do grafo antigo
			while (keys.hasMoreElements()) {
				// pega um vertice do grafo antigo
				Vertex vertex = keys.nextElement();
				//verifica se o vertice tambem pertence ao novo vertice
				if (vertex != null && vertex.getId().equals(newVertex.getId())) {
					// se sim
					foundVertex = true;
					Vector<Vertex> newLinks = newGraph.get(newVertex);
					// verifica todos os links novo deste vertice que coincide
					while (newLinks.size() > 0) {
						Vertex newLink = newLinks.remove(0);
						boolean linkFound = false;
						// pega os links do vertice antigo
						Vector<Vertex> links = graph.get(vertex);
						for (int i = 0; i < links.size(); i++) {
							Vertex link = links.elementAt(i);
							if (link != null && link.getId().equals(newLink.getId())) {
								linkFound = true;
								break;
							}
						}
						// se nao coincidir adiciona a lista de links
						if (! linkFound)
							links.add(newLink);
					}
				}
				//senao
				else {
					
				}
			}
			if (! foundVertex) {
				if (newGraph != null && newGraph.get(newVertex) != null)
					graph.put(newVertex, newGraph.get(newVertex));
			}
		}
	}
	
	/**
	 * Método utilizado para resgatar um vértice do grafo
	 * 
	 * @param id
	 * @return
	 */
	private synchronized Vertex getVertex(String id) {
		Enumeration<Vertex> keys = graph.keys();
		while (keys.hasMoreElements()) {
			Vertex vertex = keys.nextElement();
			if (vertex != null && vertex.getId().equals(id))
				return vertex;
			Vector<Vertex> values = graph.get(vertex);
			for (int i = 0; values != null && i < values.size(); i++)
				if (values.elementAt(i).getId().equals(id))
					return values.elementAt(i);
		}
		return null;
	}
	
	/**
	 * M�todo utilizado para adicionar uma aresta do v�rtice a para o v�rtice b
	 * 
	 * @param a
	 * @param b
	 */
	public synchronized void addLink(String a, String b) {
		Vertex vertexA = getVertex(a);
		Vertex vertexB = getVertex(b);
		if (vertexA == null) {
			vertexA = new Vertex(a);
			Vector<Vertex> destiny = new Vector<Vertex>();
			if (vertexB == null)
				vertexB = new Vertex(b);
			destiny.add(vertexB);
			graph.put(vertexA, destiny);
		}
		else {
			Vector<Vertex> destiny = graph.get(vertexA);
			if (vertexB == null)
				vertexB = new Vertex(b);
			if (destiny == null)
				destiny = new Vector<Vertex>();
			if (! destiny.contains(vertexB)) 
				destiny.add(vertexB);
			graph.put(vertexA, destiny);
		}
	}
	
	/**
	 * M�todo utilizado para remover uma aresta existente do v�rtice a para o v�rtice b
	 * 
	 * @param a
	 * @param b
	 */
	public synchronized void removeLink(String a, String b) {
		Vertex vertexA = getVertex(a);
		Vertex vertexB = getVertex(b);
		if (vertexA != null && vertexB != null) {
			Vector<Vertex> destiny = graph.get(vertexA);
			destiny.remove(vertexB);
		}
	}
	
	/**
	 * M�todo utilizado para remover um v�rtice da estrutura de dados
	 * 
	 * @param id
	 */
	public synchronized void removerVertex(String id) {
		Enumeration<Vertex> keys = graph.keys();
		while (keys.hasMoreElements()) {
			Vertex vertex = keys.nextElement();
			Vector<Vertex> values = graph.get(vertex);
			for (int i = 0; values != null && i < values.size(); i++)
				if (values.elementAt(i).getId().equals(id)) {
					values.removeElementAt(i);
					i--;
				}
			graph.put(vertex, values);
			if (vertex != null && vertex.getId().equals(id))
				graph.remove(vertex);
		}
	}
	
	/**
	 * M�todo utilizado para deixar todos os v�rtices na cor branca
	 */
	private synchronized void resetColors() {
		Enumeration<Vertex> keys = graph.keys();
		while (keys.hasMoreElements()) {
			Vertex vertex = keys.nextElement();
			vertex.setColor(Vertex.WHITE);
			Vector<Vertex> values = graph.get(vertex);
			for (int i = 0; values != null && i < values.size(); i++)
				values.elementAt(i).setColor(Vertex.WHITE);
		}
	}
	
	/**
	 * M�todo utilizado para resgatar os v�rtices envolvidos em um ciclo a partir de um v�rtice
	 * 
	 * @param id
	 * @return
	 */
	public synchronized Vector<String> getCircle(String id) {
		Vector<String> vertex = new Vector<String>();
		vertex = depthFirstSearchCircle(id, vertex);
		resetColors();
		circle = false;
		//for (int i = 0; i < vertex.size(); i++)
		//	System.out.println(vertex.elementAt(i));
		return vertex;
	}
	
	/**
	 * M�todo utilizado para resgatar os v�rtices existentes na estrutura de dados
	 * 
	 * @return
	 */
	public synchronized Vector<String> getVertices() {
		Vector<String> vertices = new Vector<String>();
		Enumeration<Vertex> keys = graph.keys();
		while (keys.hasMoreElements()) {
			Vertex vertex = keys.nextElement();
			vertices.add(vertex.getId());
		}
		return vertices;
	}
	
	/**
	 * M�todo para testar se o grafo tem algum ciclo
	 * 
	 * @param id
	 * @return
	 */
	public synchronized boolean isCircle(String id) {
		return (getCircle(id).size() != 0);
	}
	
	/**
	 * M�todo utilizado para verificar a exist�ncia de um ciclo utilizado o algoritmo de busca em profundidade
	 * 
	 * @param id
	 * @param visits
	 * @return
	 */
	private synchronized Vector<String> depthFirstSearchCircle(String id, Vector<String> visits) {
		if (circle)
			return visits;
		Vertex v = getVertex(id);
		v.setColor(Vertex.BLACK);
		if (! visits.contains(v.getId()))
			visits.add(id);
		else {
			while (! visits.elementAt(0).equals(id))
				visits.remove(0);
			circle = true;
			return visits;
		}
		Vector<Vertex> links = graph.get(v);
		for (int i = 0; links != null && i < links.size(); i++) {
			Vertex w = links.elementAt(i);
			if (w.getColor() == Vertex.WHITE || visits.contains(w.getId()))
				depthFirstSearchCircle(w.getId(), visits);
			if (circle)
				return visits;
		}
		return visits;
	}
	
	/**
	 * M�todo utilizado para criar um novo grafo
	 */
	public synchronized void clear() {
		graph = new Hashtable<Vertex, Vector<Vertex>>();
		circle = false;
	}
	
	/**
	 * Método utilizado para pegar os ids dos links do vertice id
	 * 
	 * @param id
	 * @return
	 */
	public synchronized Vector<String> getLinks(String id) {
		Enumeration<Vertex> keys = graph.keys();
		while (keys.hasMoreElements()) {
			Vertex item = keys.nextElement();
			Vector<Vertex> values = graph.get(id);
			if (values == null)
				return new Vector<String>();
			Vector<String> result = new Vector<String>();
			for (int i = 0; i < values.size(); i++)
				result.add(values.elementAt(i).getId());
		}
		return new Vector<String>();
	}
	
	public static void main(String[] args) {

	}
	
	/**
	 * 
	 * @author Leonardo Oliveira Moreira
	 *
	 * Classe utilizada para representar um vértice em um grafo
	 */
	class Vertex implements Serializable {
		
		public static final int WHITE = 0;
		public static final int BLACK = 1;
		
		private String id;
		private int color;
		
		public Vertex(String id) {
			color = WHITE;
			this.id = id;
		}

		public int getColor() {
			return color;
		}

		public void setColor(int color) {
			this.color = color;
		}

		public String getId() {
			return id;
		}
		
	}
	
}
